package algorithm.sort;

import java.util.Arrays;

import static algorithm.sort.SortUtil.swap;

/**
 * 冒泡排序
 *
 * @author hck
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {6, 8, 1, 9, 2, 5, 4, 3, 7};
        System.out.println(Arrays.toString(array));
        bubbleSortV1(array);
        System.out.println("-------------------------");
        bubbleSortV2(array);
        System.out.println("-------------------------");
        bubbleSortV3(array);
    }

    /**
     * 最简版冒泡排序,走完所有趟数.
     * 时间复杂度为 O(N^2)
     */
    public static void bubbleSortV1(int[] input) {
        System.out.println("最简版冒泡排序,走完所有趟数.");
        int[] array = getArrayCopy(input);
        int len = array.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - 1; j++) {
                count++;
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(array));
        System.out.println("次数:" + count);
    }

    /**
     * 冒泡排序优化版,由于每一趟后,最后的数都已是有序的,所以不需要遍历
     * 时间复杂度为 O(N^2)
     */
    public static void bubbleSortV2(int[] input) {
        System.out.println("冒泡排序v2,减少已经有序的再次遍历.");
        int[] array = getArrayCopy(input);
        int len = array.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            //  减少不必要的遍历
            for (int j = 0; j < len - i - 1; j++) {
                count++;
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(array));
        System.out.println("次数:" + count);
    }

    /**
     * 由于在排序中,可能出现提前有序,导致一次交换都没有的情况,这时可以提前结束冒泡
     * @param input
     */
    public static void bubbleSortV3(int[] input) {
        System.out.println("冒泡排序v3,已经有序的情况下提前结束遍历.");
        int[] array = getArrayCopy(input);
        int len = array.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            //  如果某一趟遍历一次交换都没有发生,说明当前数组已经有序
            boolean flag = true;
            for (int j = 0; j < len - i - 1; j++) {
                count++;
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        System.out.println(Arrays.toString(array));
        System.out.println("次数:" + count);
    }

    private static int[] getArrayCopy(int[] input) {
        int[] array = new int[input.length];
        System.arraycopy(input, 0, array, 0, input.length);
        return array;
    }
}
